#include <iostream>
#include <unordered_map>


struct ListNode
{
    int val;
    ListNode*next;
};

void solve_duplicate(ListNode*&head)
{
    // 不判空直接开始
    // 先创建哑节点
    ListNode*dummy = new ListNode{0,head};
    dummy->next = head;

    // 使用哈希表标记节点值的数量
    std::unordered_map<int,int>mp;
    ListNode*temp = head;
    while (temp)
    {
        mp[temp->val] ++;
        temp = temp->next;
    }

    // 再次遍历并删除节点
    temp = head;
    ListNode*prior = dummy;
    while (temp)
    {
        if (mp[temp->val]>1)
        {
            // 进行删除
            ListNode*to_delete = temp;
            prior->next = temp->next;
            temp = temp->next;
            delete to_delete;
        }
        else 
        {
            prior = temp;
            temp = temp->next;
        }
    }

    // 返回结果
    head = dummy->next;
    delete dummy;
}

void add_node(ListNode*&head,int data)
{
    ListNode*node = new ListNode;
    node->val = data;
    node->next = nullptr;

    if (!head)
        head = node;
    else 
    {
        ListNode*temp = head;
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = node;
    }
}

int main()
{
    ListNode*head = new ListNode;
    head->val = 2;
    head->next = nullptr;
    add_node(head,1);
    add_node(head,1);
    add_node(head,2);
    add_node(head,3);
    add_node(head,0);

    // 进行去重
    solve_duplicate(head);
    
    // 打印链表
    ListNode*temp = head;
    while (temp)
    {
        std::cout<<temp->val<<"\n";
        temp = temp->next;
    }

    return 0;
}